package com.ai.zuochengyun.phase01.class03;

import java.util.HashMap;
import java.util.Map;

public class Code10_CopyTwoPointerNode {
    private static class Node {
        int value;
        Node next;

        Node rand;

        public Node(int value) {
            this.value = value;
            this.next = null;
            this.rand = null;
        }

        public Node next(Node next) {
            this.next = next;
            this.rand = null;
            return this;
        }

        @Override
        public int hashCode() {
            return value + ((next != null) ? next.hashCode() : 0) + ((rand != null) ? rand.hashCode() : 0);
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            Node cur = (Node) obj;
            if (cur.value == this.value && cur.rand == this.rand && cur.next == this.next) {
                return true;
            }
            return super.equals(obj);
        }
    }

    /**
     * 解法一
     * @param head
     * @return
     */
    public static Node copyRandomList1(Node head) {
        Map<Node, Node> map = new HashMap<>();
        // 把当前链表的node节点都放入map缓存中
        Node cur = head;
        while (cur != null) {
            // key老节点，value新节点
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            // cur为老节点，map.get(cur)为新节点
            // 新节点的next 可以通过老节点的next找到
            map.get(cur).rand = map.get(cur.rand);
            map.get(cur).next = map.get(cur.next);
            cur = cur.next;
        }
        return map.get(head);
    }

    /**
     * 解法二：拷贝老的节点
     * @param head
     * @return
     */
    public static Node copyRandomList2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;
        // 1 -> 2 -> 3 -> null
        // 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
        while (cur != null) {
            next = cur.next;
            // 当前节点的next指向新的节点
            cur.next = new Node(cur.value);
            // 新的节点next指向老的节点的下一个节点
            cur.next.next = next;
            // 来到next节点的位置
            cur = next;
        }

        // 回到头节点，依次设置新的节点的random指针
        cur = head;
        Node copy = null;
        while (cur != null) {
            // 老的节点
            next = cur.next.next;
            // 新的节点
            copy = cur.next;
            // 如果老的节点有random指针，那么新拷贝的节点的random指针要指向老的random节点的下一个节点，才是拷贝的节点
            copy.rand = cur.rand != null ? cur.rand.next : null;
            cur = next;
        }

        // 断开新老之间的联系
        // 老节点连老节点，新节点连新节点
        // 返回新的头节点
        cur = head;
        Node res = head.next;
        while (cur != null) {
            // 新节点
            copy = cur.next;
            // 保存下一个老节点
            next = copy.next;

            // 老节点连接老节点
            cur.next = next;
            // 新节点连接新节点
            copy.next = next != null ? next.next : null;

            // 来到下一个老节点
            cur = next;
        }
        return res;
    }
}
